﻿1.随机快速排序————经典版(不推荐，会超时)
测试链接：https ://www.luogu.com.cn/problem/P1177#submit

/*
思路分析：
---交换函数（swap）：交换两个数的值，使用临时变量进行交换。
通过引用传递参数，使得交换操作直接作用于原始数组。


---划分函数（partition）：将数组 arr[l...r] 按照基准元素 x 进行划分，使得 x 左侧的所有元素小于等于 x，右侧的所有元素大于 x。
选择一个随机的基准元素 x。
使用双指针法：指针 a(越界位置) 标记当前小于等于基准的部分，指针 i 遍历整个数组。
当 arr[i] <= x 时，将其与 arr[a] 交换，并移动指针 a。
最后将基准元素 x 放置到它的正确位置，即交换 arr[a - 1] 和 arr[xi]，返回基准元素的最终位置。

 
---排序函数（sort）：递归地对数组[l...r] 范围进行排序。
如果范围无效（l >= r），则不需要排序，直接返回。
随机选择一个基准元素 x。
调用 partition 函数，将数组划分为两部分，并返回基准元素 x 的最终位置 mid。
递归地对基准元素左侧[l...mid - 1] 和右侧[mid + 1...r] 进行排序。




---时间复杂度分析：
--最坏时间复杂度： O(n²)，如果每次划分的基准都导致极端不平衡的划分（例如基准元素是最小或最大），
递归的深度将达到 O(n)，导致时间复杂度为 O(n²)。

--平均时间复杂度： O(n log n)，期望情况下，随机化基准选择可以使每次划分的时间复杂度接近 O(log n)，
因此整个排序的期望时间复杂度为 O(n log n)。
*/



//非核心代码模式：
测试链接：https://www.luogu.com.cn/problem/P1177#submit

#include<iostream>
using namespace std;

const int MAXN = 100001; // 数组最大长度
int arr[MAXN];            // 存储数组的容器
int n;                    // 数组的元素个数

// 交换函数：交换两个数的值（可以不用手搓）
// 通过引用传递参数，直接在原始数组中交换值
void swap(int& a, int& b) 
{
    int number = a; // 临时变量存储a的值
    a = b;          // 将b赋值给a
    b = number;     // 将a的值赋给b
}

// 划分函数：
// 将数组[l...r]范围中的数字，按照x进行划分，使得x左边的数字都小于等于x，x右边的数字都大于x
// 输入：l, r 数组的左、右边界；x 基准元素
// 输出：返回基准元素最终所在的位置
int partition(int l, int r, int x)
{
    int a = l;         // a是当前小于等于x部分的边界（越界位置）
    int xi = 0;        // 记录基准元素的初始位置
    int i = l;         // 遍历指针，遍历数组中的每一个元素

    // 遍历数组，调整元素位置，使得小于等于x的元素移到左边
    while (i <= r) 
    {
        if (arr[i] <= x) 
        {  
            // 如果当前元素小于等于基准元素x
            // 将当前元素与a位置的元素交换
            swap(arr[a], arr[i]);  

            // 如果交换的元素就是基准元素x，记录下基准元素的位置
            //(这一步是为了 第一次划分完后，将等于x的元素放到a位置)
            if (arr[a] == x) 
            {
                xi = a;
            }

            a++; // 增加小于等于x部分的边界
            i++; // 遍历指针前移
        }
        else 
        {
            i++; // 当前元素大于x，继续向后移动
        }

        //保证[l,a-1] 区间内 存储的是 小于等于x的元素
        //[a,r] 区间内 存储的是 大于x的元素
    }

    // 最后，基准元素放回正确的位置
    swap(arr[a - 1], arr[xi]);
    return a - 1; // 返回基准元素的最终位置
}


// 排序函数：对数组[l...r]范围内的数字进行排序
// 采用随机基准元素的快速排序算法
// 输入：l, r 数组的左、右边界
void sort(int l, int r) 
{
    // 1.范围不存在—不用排序
    // 2.只有一个数—不用排
    if (l >= r)
    {
        return;
    }

    // 随机选择一个基准元素x
    // 选择范围内的一个随机数作为基准
    
    // 注意这里的随机数选取：
    //1.rand() 是 C++ 中的一个标准库函数，用于生成一个伪随机整数。
    // 它返回一个在 0 到 RAND_MAX 之间的整数（RAND_MAX 是一个常量，通常是 32767）。

    //2.rand() 生成的结果通过 % (r - l + 1) 进行取模操作，确保结果的范围在 [0 ,(r - l)] 之间。

    //3.然后将这个随机数加上 l，即将其偏移到 [l, r] 范围内
    //得到 [l, r] 范围内的一个随机元素x==arr[?]。
    int x = arr[l + rand() % (r - l + 1)];

    // 调用划分函数进行分区
    // 划分后的数组，左边的元素 <= x，右边的元素 > x
    int mid = partition(l, r, x);

    // 递归排序左侧子数组 [l, mid-1]
    sort(l, mid - 1);

    // 递归排序右侧子数组 [mid+1, r]
    sort(mid + 1, r);
}

int main() 
{
    cin >> n; // 输入数组的长度
    // 输入数组的元素
    for (int i = 0; i < n; i++)
    {
        cin >> arr[i];
    }

    // 调用排序函数对整个数组进行排序
    sort(0, n - 1);

    // 输出排序后的数组
    for (int i = 0; i < n; i++) 
    {
        cout << arr[i] << " ";
    }

    return 0;
}










——————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————————
//核心代码模式：
https ://leetcode.cn/problems/sort-an-array/

class Solution {
public:
    // 交换函数：交换两个数的值（通过引用传递）
    void swap(int& a, int& b) {
        int number = a;
        a = b;
        b = number;
    }

    // 划分函数：根据基准元素x将数组[l, r]区间划分
    int partition(vector<int>& arr, int l, int r, int x) {
        int a = l;     // a是当前小于等于x部分的边界（越界位置）
        int xi = 0;    // 记录基准元素的初始位置
        int i = l;     // 遍历指针

        // 遍历数组，调整元素位置，使得小于等于x的元素移到左边
        while (i <= r) 
        {
            if (arr[i] <= x) 
            {
                // 如果当前元素小于等于基准元素x，将当前元素与a位置的元素交换
                swap(arr[a], arr[i]);

                // 如果交换的元素就是基准元素x，记录下基准元素的位置
                if (arr[a] == x) 
                {
                    xi = a;
                }

                a++;  // 增加小于等于x部分的边界
                i++;  // 遍历指针前移
            }
            else
            {
                i++;  // 当前元素大于x，继续向后移动
            }
        }

        // 将基准元素放回正确的位置
        swap(arr[a - 1], arr[xi]);
        return a - 1; // 返回基准元素的最终位置
    }

    // 排序函数：对数组[l, r]范围内的数字进行排序
    void quickSort(vector<int>& arr, int l, int r) 
    {
        if (l >= r) return;  // 递归退出条件：范围无效或只剩一个元素

        // 随机选择一个基准元素x
        int x = arr[l + rand() % (r - l + 1)];

        // 调用划分函数进行分区，划分后的数组，左边的元素 <= x，右边的元素 > x
        int mid = partition(arr, l, r, x);

        // 递归排序左侧子数组 [l, mid-1]
        quickSort(arr, l, mid - 1);

        // 递归排序右侧子数组 [mid+1, r]
        quickSort(arr, mid + 1, r);
    }

    // 主函数：接收数组并调用快速排序
    vector<int> sortArray(vector<int>& nums) 
    {
        quickSort(nums, 0, nums.size() - 1);  // 对整个数组进行排序
        return nums;
    }
};
